package pro.softzhang.algo.lc100;

import pro.softzhang.algo.flag.difficulty.DRed;
import pro.softzhang.algo.flag.theme.TDesign;

import java.util.HashMap;
import java.util.Map;

@DRed
@TDesign
public class LC146_LRUCache {
    public static void main(String[] args) {
        LRUCache c = new LRUCache(10);
        int p = c.get(1);
        c.put(1, 1);
    }

    static class LRUCache {

        private DoublyListNode head, tail;
        private Map<Integer, DoublyListNode> map;
        private int capacity;

        public LRUCache(int capacity) {
            map = new HashMap<>();
            head = new DoublyListNode(-1, -1);
            tail = new DoublyListNode(-1, -1);
            head.next = tail;
            tail.prev = head;
            this.capacity = capacity;
        }

        public int get(int key) {
            DoublyListNode node = map.get(key);
            if(node == null) {
                return -1;
            }

            moveToTail(node, node.value);

            return node.value;
        }

        public void put(int key, int value) {
            if(map.containsKey(key)) {
                moveToTail(map.get(key), value);
                return;
            }

            if(map.size() == capacity) {
                DoublyListNode toBeDeleted = head.next;
                deleteNode(toBeDeleted);
                map.remove(toBeDeleted.key);
            }

            DoublyListNode node = new DoublyListNode(key, value);
            insertIntoTail(node);
            map.put(key, node);
        }

        private void moveToTail(DoublyListNode node, int newValue) {
            deleteNode(node);
            node.value = newValue;
            insertIntoTail(node);
        }

        private void deleteNode(DoublyListNode node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        private void insertIntoTail(DoublyListNode node) {
            tail.prev.next = node;
            node.prev = tail.prev;
            node.next = tail;
            tail.prev = node;
        }
    }

    static class DoublyListNode {
        public int key;
        public int value;
        public DoublyListNode prev;
        public DoublyListNode next;

        public DoublyListNode(int k, int v) {
            key = k;
            value = v;
        }
    }

}